package com.zyk.grate_offer.class05;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author zhangsan
 * @date 2021/5/7 21:43
 */
public class Code02_EditDistance {


    public static int minDistance(String word1, String word2) {
        return f(word1, word2, 1, 1, 1);
    }

    /**
 * s1 => s2, 最短消耗
     *
     * @param ic 插入一个字符的消耗
     * @param dc 删除一个字符的消耗
     * @param rc 替换一个字符的消耗
     * @return 最短消耗
     */
    public static int f(String str1, String str2, int ic, int dc, int rc) {
        char[] s1 = str1.toCharArray();
        char[] s2 = str2.toCharArray();

        // 1. 我前面和你整体一样, + 我删掉最后一个字符的代价     dp[i-1][j] + dc
        // 2. 我整体和你前面一样, + 我添加最后一个字符的代价     dp[i][j-1] + ic
        // 3. 我这个字符和你这个字符相等, 我的代价为我前面的字符变成你前面字符的代价.     s1[i] == s2[j] ? dp[i-1][j-1],
        //          即当前位置没有代价
        // 4. 我这个字符和你这个字符不等, 我的代价为我前面的字符变成你前面字符的代价.+替换代价    s1[i] != s2[j] ? dp[i-1] + dp[j-1] + rc

        int R = s1.length + 1;
        int C = s2.length + 1;
        int[][] dp = new int[R][C];
        // dp[0][0] = 0;    "" => "" 最小代价0
        // i:0, j:(1~C). 所需的代价只能是添加字符
        for (int c = 1; c < C; c++) {
            dp[0][c] = c * ic;
        }
        // i:(1~R) j:0. 所需的代价只能是删除字符
        for (int r = 1; r < R; r++) {
            dp[r][0] = r * dc;
        }
        // 上述四种情况
        for (int r = 1; r < R; r++) {
            for (int c = 1; c < C; c++) {
                dp[r][c] = dp[r-1][c-1] + (s1[r-1] == s2[c-1] ? 0 : rc);  // 3,4情况
                dp[r][c] = Math.min(dp[r][c], dp[r-1][c] + dc);
                dp[r][c] = Math.min(dp[r][c], dp[r][c-1] + ic);
            }
        }
        return dp[R-1][C-1];
    }


    public static void main(String[] args) {
        String str1 = "abc";
        String str2 = "ab";
        System.out.println(f(str1, str2, 5, 10, 20));
    }

}
